This invention relates in general to digital halftone systems and in particular, to an improved digital halftone system using error diffusion.
In the conventional printing process, continuous tone images are prepared for printing by exposure through a halftone screen. The resultant image will have dots of various sizes, one for each opening in the screen. These dots are larger where more light penetrates the screen and smaller where less light is present. Thus the exposure through the screen converts intensity level of the original image at the opening in the screen into a dot of appropriate diameter or size. In the digital analog of the above process, known as digital halftoning, the original image is scanned with a scanner and the data is captured in a digital computer. This data consists of binary representations of the scanned intensity or density values. Each such value, typically ranging from 0 to 255, corresponds to one scanned area or pixel of the input image. To reproduce this image on a printer capable of only printing colored dots, it is necessary to create a sensation of intensity by suitable choice of the dots to be printed.
In digital halftoning, a multi-level or continuous tone original image is scanned pixel by pixel. Signals representing the density levels of the pixels or blocks of pixels scanned are processed to provide a bi-level output for a printer. In response to the bi-level output, the printer would either print a dot or not to provide an image resembling the original.
Two types of digital halftoning techniques have been used. In one of the two types known as screening or dithering, the signals representing the density levels of the pixels or blocks of pixels of the original image scanned are multiplied by or compared to signals representing a two-dimensional screen function to provide the bi-level output. In response to the bi-level output, the printer will print or not print dots at fixed output positions. In the other type known as error diffusion, no screening function is used. Instead, the error that results in quantizing the density level of a pixel or a block of pixels (i.e. converting to a bi-level output) is taken into account when pixels or blocks of pixels in a neighborhood are subsequently converted into bi-level outputs (i.e. diffused to neighborhood pixels or blocks).
In contrast to screening or dithering, in error diffusion systems, the printer is not caused to print dots in fixed output positions; instead, the printer may print dots at whatever locations selected, and indeed the density level desired is achieved by selecting the appropriate dot spacing or wavelength corresponding to the scanned density level. Usually, the wavelength of dots to be printed by the printer varies inversely with the density level of the pixel or block of pixels scanned from the original image. Hence, when the input signal indicates a change in density level of the scanned original, the wavelength of dots to be printed also changes. The wavelength of dots to be printed as a function of the density level of the scanned image may be stored in a lookup table in the computer memory.
Thus, if the scanned density level ranges from 0 to 255, and the particular density level of the scanned image has the value "1," this means that one dot should be printed in a 16.times.16 array so that one dot should be printed on every sixteenth position in the printing direction by the printer. This in turn defines a dot wavelength of 16. In error diffusion techniques, the dot size is typically fixed, unlike screening and dithering techniques.
Error diffusion was first proposed by R. W. Floyd and L. Steinberg. Such technique is described in some detail in Section 8.2, pages 239-252 of the book "Digital Halftoning," by Robert Ulichney, Massachusetts Institute of Technology , 1987. One example of such error diffusion and algorithm proposed by Floyd and Steinberg is illustrated in FIG. 8.6(a) of Ulichney, where a rectangular grid is used in printing. Such figure shows the proportions of the error distributed to neighboring pixels when the density level at the pixel represented by the black dot is converted to a bi-level output. An error term given by 7/16th of the quantization error is distributed to the next pixel immediately to its right on the same line for printing. A weighted error given by 1/16th of the quantization error is distributed to the pixel immediately beneath the prior pixel to which error has been distributed and 5/16th and 3/15th of the quantization error are distributed to the two pixels immediately to the left, all as shown in FIG. 8.6(a) of Ulichney. This operation is known as an error filter, where weighted portions of the quantization error are distributed to four pixels as shown. It is noted that the four weights (7/16, 1/16, 5/16 and 3/16) add up to "1." When the pixel shown by the black dot is to be converted to a bi-level output, the density level of the pixel scanned is compared to a threshold (such as "128" for full range of density levels from "0" to "255"). When the density level is beneath the threshold, the printer is commanded to print a dot at such location and the quantization error is equal to the input signal representing th density level. If the input signal is greater than the threshold, then no dot is printed and the error is given by the difference between the maximum value (e.g., "255") and the input signal representing the density level of the scanned pixel. In other words, if the scanned density level at the pixel in the "x, y" position is Pval(x, y) and the converted bi-level output of the pixel is Pout(x, y), where the density level is in the range from "0" to "255," and the threshold is "T," then
if Pval(x, y)&lt;T, then PA1 Pout(x, y)=color, and PA1 Error=Pval (x, y); but PA1 if Pval(x, y)&gt;T, then PA1 Pout(x, y)=white, and PA1 Error=Pval(x, y)-255.
The error is then distributed to surrounding pixels in the manner described above.
A number of methods have been proposed for allocating the quantization error in error diffusion. In many error diffusion methods, the error is divided into fixed proportions. The Floyd and Steinberg technique described above is one example. The halftone pictures produced by such methods produce output pattern artifacts consisting of apparent curved or straight lines, known to the industry as "worms."
To reduce or eliminate the "worms," many solutions have been proposed. In U.S. Pat. No. 4,654,721 to Goertzel et al., a random fraction of the error is distributed to one neighboring block and the remainder is distributed to another neighboring block. In the article "Error Diffusion Using Random Field Models," by J. C. Dalton et al., Markov random field error diffusion algorithm is used to generate random textures for eliminating grain boundary errors associated with conventional error diffusion textures in large constant tone regions.
None of the above-described error diffusion techniques are entirely satisfactory. In particular, the highlight or dark areas where the density levels of scanned images are either very high or very low, the above-referred to patterned artifacts or "worms" are particular noticeable, even when the above-described known error diffusion techniques are employed. It is therefore desirable to provide an error diffusion system for halftoning in which the above-described difficulties are alleviated.